package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

/**
 * 0654.最大二叉树
 *
 * 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
 * ● 二叉树的根是数组中的最大元素。
 * ● 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * ● 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 * 通过给定的数组构建最大二叉树，并且输出这个树的根节点。
 *
 * 提示：
 * 给定的数组的大小在 [1, 1000] 之间。
 *
 * 构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
 * @author Liyc
 * @date 2024/1/11 10:33
 **/

public class Solution15 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }

        int maxValue = nums[leftIndex];// 最大值
        int maxIndex = leftIndex;// 最大值所在位置
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        // 根据maxIndex划分左右子树  左闭右开
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}
